package com.sheng.leetcode.year2024.month01.day22;

import org.junit.Test;

/**
 * @author by ls
 * @date 2024/1/22
 * <p>
 * 670. 最大交换<p>
 * <p>
 * 给定一个非负整数，你至多可以交换一次数字中的任意两位。返回你能得到的最大值。<p>
 * <p>
 * 示例 1 :<p>
 * 输入: 2736<p>
 * 输出: 7236<p>
 * 解释: 交换数字2和数字7。<p>
 * <p>
 * 示例 2 :<p>
 * 输入: 9973<p>
 * 输出: 9973<p>
 * 解释: 不需要交换。<p>
 * <p>
 * 注意:<p>
 * 给定数字的范围是 [0, 10^8]<p>
 */
public class LeetCode0670 {

    @Test
    public void test01() {
//        int num = 2736;
//        int num = 9973;
        int num = 98368;
        System.out.println(new Solution().maximumSwap(num));
    }
}

class Solution {
    public int maximumSwap(int num) {
        // 找到最大的那个数字，如果有多个最大的数组，拿最后的一个
        // 还需要获取到比最大数组小的，最靠前的一个所在的位置，然后进行交换
        // 还要根据大小值的所在位置，动态变换
        String str = String.valueOf(num);
        int n = str.length();
        int last = n - 1;
        // 查询左边的最小数字和右边的最大数字，满足位置条件和大小条件即可交换位置，否则继续遍历
        char[] charArray = str.toCharArray();
        int left = -1, right = n - 1;
        for (int i = n - 2; i >= 0; i--) {
            if (charArray[i] > charArray[last]) {
                last = i;
            } else if (charArray[i] < charArray[last]) {
                right = last;
                left = i;
            }
        }
        // 数字为倒序，直接返回
        if (left == -1) {
            return num;
        }
        char temp = charArray[left];
        charArray[left] = charArray[right];
        charArray[right] = temp;
        return Integer.parseInt(new String(charArray));
    }
}
